/**
 *    Copyright (C) 2008  Victor Smirnov <aist11@gmail.com>
 *
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License along
 *    with this program; if not, write to the Free Software Foundation, Inc.,
 *    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 *    See LICENSE.exceptions in the root folder of this project for possible
 *    exceptions
 *
 */


#ifndef __BITVECTOR_BTREE_TEST_HPP__
#define __BITVECTOR_BTREE_TEST_HPP__

#include <unistd.h>

#include <cppunit/extensions/HelperMacros.h>
#include <cppunit/portability/Stream.h>

#include <cubefs/core/bitvector.hpp>
#include "TestBase.hpp"

using namespace std;

namespace cubefs {
namespace core {
namespace tests {
namespace bitvector_ns {

class BTreeTest : public TestBase
{
    CPPUNIT_TEST_SUITE(BTreeTest);

    CPPUNIT_TEST(testCreatePageTree);
    CPPUNIT_TEST(testReadWrite);
    //CPPUNIT_TEST(testUDS);
    CPPUNIT_TEST(testSplit);
    //CPPUNIT_TEST(testMerge);
    CPPUNIT_TEST(testHugeCountOne);
    CPPUNIT_TEST(testRemoveSinglePage);
    CPPUNIT_TEST(testRemoveWholeTree);
    CPPUNIT_TEST(testRemoveWholeLeaf);
    
    // SegFault
    //CPPUNIT_TEST(testRemoveWholeSubtree);

    CPPUNIT_TEST_SUITE_END();

protected:


public:

    BTreeTest() {}


    void testCreatePageTree() {
        node_base* root = create_tree(3, 3, 64);

        iterator iter = get_first(root);

        index_t c;
        for (c = 0; iter.next_bitmap(); c++) {}

        CPPUNIT_ASSERT_EQUAL(81l - 1, c);

        remove_tree(root);
    }

    void testReadWrite() {
        int c;
        node_base* root = create_tree(1, 2, 888);

        iterator iter = get_first(root);

        for (c = 0; c < 80; c++) {
            iter.write(c + 0x7FAAFF00);
        }

        iter = get_first(root);

        for (c = 0; c < 80; c++) {
            int val;
            iter.read(val);
            CPPUNIT_ASSERT_EQUAL((int)(c + 0x7FAAFF00), val);
        }

        remove_tree(root);
    }

    void testHugeCountOne() {
        index_t page_size = 30000;

        node_base* root = create_tree(2, 2, page_size);
        iterator iter = get_first(root);

        csize_t prefix = 0, offset = 0;

        do {
            for (index_t c = 0; c < iter.data()->header().get_size(); c++) {
                set_bit(iter.data()->bits(), c, 1);
            }
            iter.data()->reindex(prefix, offset, 4, 0);
            offset = 0;
            update_btree(iter.data(), 0, iter.data()->header().get_size(), 0);
        }
        while (iter.next_bitmap());

        index_t size = get_key(root, 0);
        index_t rank = get_key(root, 1);
        index_t bitsize = get_key(root, 2);

        CPPUNIT_ASSERT_EQUAL(page_size * pow(2, 3), size);
        CPPUNIT_ASSERT_EQUAL(page_size * pow(2, 3), rank);
        CPPUNIT_ASSERT_EQUAL(page_size * pow(2, 3), bitsize);

        iter = get_first(root);

        //bool inserted, hasnt_label;
        csize_t ones = iter.count_one_fw().count;
        CPPUNIT_ASSERT_EQUAL((csize_t)rank, ones);

        iter = get_last(root);

        prefix = 0;
        offset = 0;

        set_bit(iter.data()->bits(), iter.data()->header().get_size() - 1, 0);
        iter.data()->reindex(prefix, offset, 4, 0);

        update_btree(iter.data(), 0, -1, 0);

        size = get_key(root, 0);
        rank = get_key(root, 1);
        bitsize = get_key(root, 2);

        CPPUNIT_ASSERT_EQUAL(page_size * pow(2, 3),     size);
        CPPUNIT_ASSERT_EQUAL(page_size * pow(2, 3) - 1, rank);
        CPPUNIT_ASSERT_EQUAL(page_size * pow(2, 3),     bitsize);

        iter = get_first(root);

        ones = iter.count_one_fw().count;
        CPPUNIT_ASSERT_EQUAL((csize_t)rank, ones);

        iter = get_last(root);
        prefix = 0;
        offset = 0;

        index_t idx0 = ((page_size/512)*512);

        set_bit(iter.data()->bits(), idx0 , 0);
        iter.data()->reindex(prefix, offset, 4, 0);

        update_btree(iter.data(), 0, -1, 0);

        size = get_key(root, 0);
        rank = get_key(root, 1);
        bitsize = get_key(root, 2);

        CPPUNIT_ASSERT_EQUAL(page_size * pow(2, 3),     size);
        CPPUNIT_ASSERT_EQUAL(page_size * pow(2, 3) - 2, rank);
        CPPUNIT_ASSERT_EQUAL(page_size * pow(2, 3),     bitsize);

        iter = get_first(root);
        ones = iter.count_one_fw().count;
        CPPUNIT_ASSERT_EQUAL((csize_t)rank + 2 - (page_size - idx0), ones);

        remove_tree(root);
    }

    void testUDS() {
        index_t page_size = 30000;
        node_base* root = create_tree(2, 2, page_size);

        index_t original_bitsize = get_key(root, 2);

        iterator iter = get_first(root);

        value_buffer<int> one(1), zero(0), label(9);
        index_t total_size = 0, total_rank = 0, total_bitsize = 0;

        for (index_t c = 1; c < 256; c++) {
            for (index_t d = 0; d < c; d++) {
                iter.write_bits(one, 0, 1);
            }

            iter.write_bits(zero, 0, 1);

            for (index_t d = 0; d < c; d++) {
                iter.write_bits(label, 0, 4);
            }

            iter.write_bits(zero, 0, 1);

            total_rank += c;
            total_bitsize += c + 1;

            total_size += c + 2 + c * 4;
        }

        iter = get_first(root);

        csize_t prefix = 0, offset = 0;


        do {
            index_t rank0 = iter.data()->header().get_rank();
            index_t bitsize0 = iter.data()->header().get_bitsize();

            iter.data()->reindex(prefix, offset, 4, 0);
            offset -= iter.data()->header().get_size();

            index_t rank = iter.data()->header().get_rank();
            index_t bitsize = iter.data()->header().get_bitsize();

            update_btree(iter.data(), 0, rank - rank0, bitsize - bitsize0);
        }
        while (iter.next_bitmap());

        index_t rank = get_key(root, 1);
        index_t bitsize = get_key(root, 2);

        CPPUNIT_ASSERT_EQUAL(total_rank,    rank);
        CPPUNIT_ASSERT_EQUAL(total_bitsize, bitsize - (original_bitsize - total_size));

        iter = get_first(root);

        for (index_t c = 1; c < 256; c++) {
            csize_t cnt = iter.count_one_fw().count;
            CPPUNIT_ASSERT_EQUAL((csize_t)c, cnt);

            iter.move_fw(cnt * 4 + 2);
        }

        remove_tree(root);
    }

     node_base *insert_into(node_base* root, index_t leaf_number, bool &node_created, index_t page_size) {
        bv bv0(mgr, root->id());
        bv0.max_node_capacity() = 2;

        iterator iter = get_first(root);

        for (index_t d = 0; d < leaf_number; d++) {
            iter.next_leaf();
        }

        node_base* leaf = iter.page();
        BV_NODE_CAST2(leaf,
            index_t count = __leaf->map().size();
            if (count == 1) {
                node_created = true;

                __leaf->map().size() = 2;

                bitmap_node *bitmap = new (mgr, txn) bitmap_node;
                __leaf->map().data(1)   = bitmap->id();
                bitmap->parent_id()     = __leaf->id();
                bitmap->parent_idx()    = 1;

                csize_t prefix = 0;
                csize_t offset = 0;
                fill_bitmap(bitmap, prefix, offset, page_size);

                count++;
            }
            else {
                node_created = false;
            }

            bv0.split_btree_node(__leaf, count / 2, 0, txn);
        );

        return bv0.get_root(txn);
    }


    void testSplit() {
        index_t page_size = 100;
        node_base *root = create_tree(0, 2, page_size);

        CPPUNIT_ASSERT_EQUAL((csize_t)200, get_key(root, 0));

        index_t count = 1024;
        index_t inserts = 0;

        for (index_t c = 0; c < count; c++) {
            index_t split_idx = (c == 0 ? 0 : random() % c);

            bool inserted;
            root = insert_into(root, split_idx, inserted, page_size);
            if (inserted) {
                inserts++;
            }

            //check_node(root, (inserts + 2)*page_size, 0, (inserts + 2)*page_size, 0);
        }

        remove_tree(root);
    }

    void testMerge() {
        index_t page_size = 100;

        index_t levels = 9;

        node_base *root = create_tree(levels, 2, page_size);

        index_t leafs = pow(2, levels + 1);

        bv bv0 (mgr, root->id());
        bv0.max_node_capacity() = 2;

        index_t cnt = 0;

        while (bv0.get_root(txn) != NULL && cnt < 2000) {
            cnt++;

            root = bv0.get_root(txn);
            iterator iter = get_first(root);
            index_t bitmaps = get_key(root, 0) / page_size;
            index_t bitmap = random() % bitmaps;

            for (int c=0; c < bitmap; c++) {
                iter.next_bitmap();
            }

            bv::update_btree_nodes(
                iter.page(),
                iter.data()->parent_idx(),
                -iter.data()->header().get_size(),
                -iter.data()->header().get_rank(),
                -iter.data()->header().get_bitsize(),
                mgr,
                txn
            );

            node_base *node = iter.page();
            bv0.remove_space(node, iter.data()->parent_idx(), 1, txn);
            BV_NODE_CAST2(node, __node->map().reindex());


            if (bv::get_children_count(iter.page()) == 0) {
                node_base *node1 = iter.page();
                index_t parent_idx = 0;
                while (bv::get_children_count(node1) <= 1 && !node1->is_root()) {
                    node_base *tmp = node1;
                    parent_idx = tmp->parent_idx();
                    node1 = bv::get_parent(node1, mgr, txn);
                    mgr.free(txn, tmp);
                }

                BV_NODE_CAST2(node1,
                    if (!__node1->is_root() || __node1->map().size() > 1) {
                        bv0.remove_space(node1, parent_idx, 1, txn);
                        __node1->map().reindex();
                    }
                    else {
                        CPPUNIT_ASSERT(__node1->is_root());
                        mgr.free(txn, __node1);
                        bv0.root() = 0;
                    }
                );
            }
            else if (bv0.get_capacity(iter.page()) >= bv0.get_max_capacity(iter.page()) / 2 ) {
                iterator iter1 = iter;
                iterator iter2 = iter;

                if (iter1.next_leaf() && bv0.merge_btree_nodes(iter.page(), iter1.page(), txn)) {

                }
                else if (iter2.prev_leaf()) {
                    bv0.merge_btree_nodes(iter2.page(), iter.page(), txn);
                }
            }

            leafs--;

            if (bv0.get_root(txn) != NULL) {
                //check_node(bv0.get_root(txn), leafs * page_size, 0, leafs * page_size, 0);
            }
        }



        CPPUNIT_ASSERT(bv0.root().is_null());
    }

    void testRemoveSinglePage() {
        index_t page_size = 100;

        index_t levels = 1;

        node_base *root = create_tree(levels, 3, page_size);

        bv bv0 (mgr, root->id());
        bv0.max_node_capacity() = 3;

        root = bv0.get_root(txn);

        csize_t size1    = bv::get_max_key(root, 0);
        csize_t rank1    = bv::get_max_key(root, 1);
        csize_t bitsize1 = bv::get_max_key(root, 2);

        iterator from = get_first(root);

        iterator to = from;
        to.next_bitmap();

        bv0.remove_pages(from.page(), from.data()->parent_idx() - 1, to.page(), to.data()->parent_idx(), txn);

        root = bv0.get_root(txn);

        check_node(root, size1 - page_size, rank1, bitsize1 - page_size, 0);

        remove_tree(root);
    }

    void testRemoveWholeTree() {
        index_t page_size = 100;

        index_t levels = 3;

        node_base *root = create_tree(levels, 3, page_size, 1);

        bv bv0 (mgr, root->id());
        bv0.max_node_capacity() = 3;

        root = bv0.get_root(txn);

        iterator from = get_first(root);
        iterator to = get_last(root);;


        bv0.remove_pages(from.page(), from.data()->parent_idx() - 1, to.page(), to.data()->parent_idx() + 1, txn);

        root = bv0.get_root(txn);

        CPPUNIT_ASSERT(root == NULL);
    }

    void testRemoveWholeLeaf() {
        index_t page_size = 100;

        index_t levels = 3;

        node_base *root = create_tree(levels, 3, page_size);

        csize_t size1    = bv::get_max_key(root, 0);
        csize_t rank1    = bv::get_max_key(root, 1);
        csize_t bitsize1 = bv::get_max_key(root, 2);

        bv bv0 (mgr, root->id());
        bv0.max_node_capacity() = 3;

        root = bv0.get_root(txn);

        iterator from = get_first(root);
        iterator to = from;

        to.next_leaf();

        bv0.remove_pages(from.page(), from.data()->parent_idx() - 1, to.page(), to.data()->parent_idx(), txn);

        root = bv0.get_root(txn);

        check_node(root, size1 - page_size*3, rank1, bitsize1 - page_size*3, 0);
    }

    void testRemoveWholeSubtree() {
        index_t page_size = 100;

        index_t levels = 3;

        node_base *root = create_tree(levels, 3, page_size);

        csize_t size1    = bv::get_max_key(root, 0);
        csize_t rank1    = bv::get_max_key(root, 1);
        csize_t bitsize1 = bv::get_max_key(root, 2);

        bv bv0 (mgr, root->id());
        bv0.max_node_capacity() = 3;

        root = bv0.get_root(txn);

        iterator from = get_first(root);
        iterator to = from;

        to.next_leaf();
        to.next_leaf();
        to.next_leaf();
        to.prev_bitmap();

        bv0.remove_pages(from.page(), from.data()->parent_idx() - 1, to.page(), to.data()->parent_idx() + 1, txn);

        root = bv0.get_root(txn);

        check_node(root, size1 - page_size*9, rank1, bitsize1 - page_size*9, 0);
    }
};

} //bitvector_ns
} //tests
} //core
} //cubefs

#endif

